package main

import "fmt"

// leetcode 0749.隔离病毒
// 每天只能隔离一个被感染区域
// 病毒每晚会扩散
// BFS，可以得到感染区域
// 每次计算威胁最大的进行隔离
// 最大威胁的定义：边界区域最大，可扩展方向最多
// 	存储变量：相邻未感染区域0的位置和个数【被威胁区】
// 	如果为该区域设置防火墙，则需要防火墙的个数

// 对于前者，我们在广度优先搜索的过程中，只要在扩展 1 时搜索相邻的 0，就可以把这个 0 对应的位置放在一个哈希集合中。
// 这里使用哈希集合的原因是同一个 0 可能会和多个 1 相邻，可以防止重复计算。
// 同时，由于多个 1 可能出现在不同的感染区域中，如果通过修改矩阵 isInfected 的形式来标记这些 0，会使得代码编写较为麻烦。

// 对于后者，计算的方法是类似的，在扩展 1 时如果搜索到相邻的 0，那么我们就需要在 1 和 0 之间的这条网格边上建一个防火墙。
// 同一个 0 和多个 1 相邻，就需要建立多个防火墙，因此我们只需要使用一个变量在广度优先搜索的过程中计数即可，无需考虑重复的情况。

// 在广度优先搜索完成后，如果我们没有发现任何感染区域，说明区域内不存在病毒，我们直接返回 0 作为答案。
// 否则，我们需要找到「对未感染区域的威胁最大」的区域，这里只需要找出对应的哈希集合的  大小最大  的那块区域即可。

// 在确定了区域（假设是第 idx 块区域）后，我们把矩阵中所有的 -idx 都变成 2，这样可以不影响任何搜索和判断；除此之外的所有负数都恢复成 1。
// 此外，所有哈希集合中存储的（除了第 idx 块区域对应的以外）所有相邻位置都需要从 0 变成 1，表示病毒的传播。

// 最后，如果我们发现区域一共只有一块，那么这次防火墙建立后，不会再有病毒传播，可以返回答案；否则我们还需要继续重复执行上述的所有步骤。

type pair struct{ x, y int }
// 四个可扩展方向，上下左右
var dirs = []pair{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

func containVirus(isInfected [][]int) (ans int) {
	// m*n
    m, n := len(isInfected), len(isInfected[0])
    for {
        neighbors := []map[pair]struct{}{}
        firewalls := []int{}
		// 遍历每个格子，BFS搜索被感染区域
        for i, row := range isInfected {
            for j, infected := range row {
                if infected != 1 {
                    continue
                }
				// 从被感染区域BFS，得到一个感染区域；感染区域
                q := []pair{{i, j}}
				// 每个0格可能与多个1相邻，如果改变数字，则会很复杂；比如0与一个1相邻就++
                neighbor := map[pair]struct{}{}
				// 应设置的防火墙的数量；idx标识区域
                firewall, idx := 0, len(neighbors)+1
                row[j] = -idx
                for len(q) > 0 {
                    p := q[0]
                    q = q[1:]   // 队头出
					// 向四个方向遍历
                    for _, d := range dirs {
						// 越界检查
                        if x, y := p.x+d.x, p.y+d.y; 0 <= x && x < m && 0 <= y && y < n {
                            if isInfected[x][y] == 1 {
								// 沿着1继续
                                q = append(q, pair{x, y})
								// 避免重复遍历
                                isInfected[x][y] = -idx
                            } else if isInfected[x][y] == 0 {
								// 遇到邻居0
                                firewall++
                                neighbor[pair{x, y}] = struct{}{}
                            }
                        }
                    }
                }
                neighbors = append(neighbors, neighbor)
                firewalls = append(firewalls, firewall)
            }
        }

        if len(neighbors) == 0 {
            break
        }
		// 计算威胁最大的
        idx := 0
        for i := 1; i < len(neighbors); i++ {
            if len(neighbors[i]) > len(neighbors[idx]) {
                idx = i
            }
        }
		// 对威胁最大的加防火墙
        ans += firewalls[idx]
		// 恢复1
        for _, row := range isInfected {
            for j, v := range row {
                if v < 0 {
                    if v != -idx-1 {
                        row[j] = 1
                    } else {
                        row[j] = 2
                    }
                }
            }
        }

        for i, neighbor := range neighbors {
            if i != idx {
                for p := range neighbor {
                    isInfected[p.x][p.y] = 1
                }
            }
        }

        if len(neighbors) == 1 {
            break
        }
    }
    return
}

func main(){
	// 输入: isInfected = [[0,1,0,0,0,0,0,1],[0,1,0,0,0,0,0,1],[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0]]
	// 输出: 10
	isInfected := [][]int{
		{0,1,0,0,0,0,0,1},{0,1,0,0,0,0,0,1},{0,0,0,0,0,0,0,1},{0,0,0,0,0,0,0,0},
	}
	ans := 10
	res := containVirus(isInfected)
	if ans==res {
		fmt.Println("Pass")
	}

}